# 2002. 两个回文子序列长度的最大乘积
# 中等
# 相关标签
# 相关企业
# 提示
# 给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。
#
# 请你返回两个回文子序列长度可以达到的 最大乘积 。
#
# 子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串 。


class Solution(object):
    def __init__(self):
        self.max_product = None

    def maxProduct(self, s):
        """
        :type s: str
        :rtype: int
        """
        self.max_product = 0
        self.iterate_substring(s, "", "", 0)
        return self.max_product

    def iterate_substring(self, origin_str, sub_string1, substring_2, index):
        if self.is_cycle_string(sub_string1) and self.is_cycle_string(substring_2):
            self.max_product = max(self.max_product, len(sub_string1)*len(substring_2))
        if index >= len(origin_str):
            return

        self.iterate_substring(origin_str, sub_string1 + origin_str[index], substring_2, index + 1)
        self.iterate_substring(origin_str, sub_string1, substring_2 + origin_str[index], index + 1)
        self.iterate_substring(origin_str, sub_string1, substring_2, index + 1)

    def is_cycle_string(self, sub_string):
        for i in range(0,int(len(sub_string)/2)):
            if sub_string[i] != sub_string[len(sub_string)-i-1]:
                return False
        return True
